package com.atguigu.search;

import java.util.Arrays;

/**
 * @author durant
 * @create 2021-11-16 12:18
 */
public class FibonacciSearch {
    public static final int maxSize = 20;
    public static void main(String[] args) {
        int[] arr = {1,8, 10, 89, 1000, 1234};
        int i = fibSearch(arr, 89);
        System.out.println(i);
    }
    public static int[] fibnaci() {
        int[] arr = new int[maxSize];
        if (maxSize <= 0) {
            return null;
        }
        arr[0]=1;
        arr[1]=1;
        for (int i = 2; i <maxSize; i++) {
            arr[i] =arr[i-1] +arr[i-2];
        }
        return arr;
    }

    /**
     *@param a 数组
     *@param key 我们需要查找的元素
     *@return int
     */
    public static int fibSearch(int[] a, int key){
        int low = 0;
        int high = a.length - 1;
        int k = 0; // 表示斐波那契数列分割数值的下标
        int mid = 0 ;
        int[] fib = fibnaci();
        // 获取覅波纳奇分割数值的下标
        // 但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。
        while (high >fib[k] - 1){// 当fib[k]-1 的长度大于high时，那么退出
            k++;
        }
        // 因为f[k] 值可能大于a的长度，
        // 需要将比a长的部分 设定出来
        int[] temp = Arrays.copyOf(a, fib[k]);
        for (int i = high+1; i <temp.length ; i++) {
            temp[i] = a[high];// 将多出来的部分用数组最大的数即a[high]来填充
        }
        while (low <= high){
            mid = low + fib[k - 1] -1;
            if (key < temp[mid]){// 向左边查找
                high = mid -1;
                k--;//
            }else if (key > temp[mid]){// 向右边查找
                low = mid + 1;
                k = k - 2;//
            }else{ // 找到了
                // 需要确定返回的是哪个下标
                if (mid <= high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }
}
